package 单调栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/18 14:03
 */
public class lc84柱状图中最大的矩形 {



    /*
     特殊的 basecase
     [2,3,4,2]
     [2,1,1,1,2]


     说句实话, 这个题有点绕

     以为 只需要计算一侧 就可以, 只计算 右边界, 无法 得出 正确的结果
     */

    public int solve(int heights[]){
        int len, ans = 0;
        int map[] = new int[len = heights.length];
        Deque<Integer> stack = new ArrayDeque<>();


        for(int i = 0;i < len;i++){

            while(!stack.isEmpty() && heights[stack.peekLast()] > heights[i]){
                Integer last = stack.removeLast();
                map[last] = i;
                ans = Math.max(ans,(i - last) * heights[last]);
            }
            //add
            stack.addLast(i);
        }
        // 单调 非递减的 特殊情况, 没有考虑到
        while(!stack.isEmpty()){
           int last =  stack.removeLast();
           ans = Math.max(ans,(len - last) * heights[last]);
        }

        return ans;
    }

    // 两个边界都需要计算 , 别他妈挣扎了, 加哨兵 是最简单的方式
    // 这个题的难点在于 , 有重复元素的存在!
    public int solve2(int heights[]){
        int len = heights.length,ans = 0;
        // 其实 使用哨兵 ,好像根本就不用修改原数组

        Deque<Integer> stack = new ArrayDeque<>();
//        stack.addLast(0); // 体会这个 的好处
        for(int i = 0;i < len;i++){

            while(!stack.isEmpty() && heights[stack.peekLast()] > heights[i]){
                int last = stack.removeLast();
                int l =  stack.isEmpty() ? -1 : stack.peekLast();
                ans = Math.max(ans,(i - l - 1) * heights[last]);
            }
            stack.addLast(i);
        }
        while(!stack.isEmpty() && heights[stack.peekLast()] > 0){
            int last = stack.removeLast();
            int l =  stack.isEmpty() ? -1 : stack.peekLast();
            ans = Math.max(ans,(len - l - 1) * heights[last]);
        }

        return ans;
    }

}
/*
 这个是什么 操作 ,我没太  看明白 ?
 颠覆我的认知?
 */
class Solution {
    public static int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] stack = new int[height.length];
        int maxArea = Integer.MIN_VALUE;
        int si = -1;
        for (int i = 0; i < height.length; i++) {
            while(si != -1 && height[stack[si]] >= height[i]) {
                int j = stack[si--];
                int left = si == -1 ? -1 : stack[si];
                int ans = (i - left -1) * height[j];
                maxArea = Math.max(maxArea, ans);
            }
            stack[++si] = i;
        }
        while(si != -1 ) {
            int j = stack[si--];
            int left = si == -1 ? -1 : stack[si];
            int ans = (height.length - left -1) * height[j];
            maxArea = Math.max(maxArea, ans);
        }

        return maxArea;
    }



}
